// Problem: 
// Contest: 
// URL: 
// Memory Limit: 
// Time Limit: 
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
signed main()
{
	int t=1;
	cin>>t;
	while(t--)
	{
		int a,b;
		cin>>a>>b;
		if(a==b||(a&b)==0)cout<<1<<endl;
		else if(__gcd(a,b)==a||__gcd(a,b)==b
			||(__gcd(a,b)&a)==0
			||(__gcd(a,b)&b)==0)cout<<2<<endl;
		else if((a&b)==a||(a&b)==b
			||((a&b)&b)==0
			||((a&b)&a)==0)cout<<2<<endl;
		else if((a|b)==a||(a|b)==b
			||((a|b)&b)==0
			||((a|b)&a)==0)cout<<2<<endl;
		else cout<<3<<endl;
	}
	return 0;
}
